package study.datastructure.link.leetcode;

import lombok.val;

class Client82 {
    /**
     * 给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表
     *
     * @param head
     * @return
     */
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode dHead = new ListNode(-1, head);
        ListNode prev = dHead;

        ListNode p1 = head;
        ListNode p2 = head.next;

        while (p2 != null) {
            if (p1.val == p2.val) {
                // 中间重复 //尾重复 多个相同值 移动指针
                while (p2.next != null && p1.val == p2.next.val) {
                    p1 = p1.next;
                    p2 = p2.next;
                }

                if (p2.next == null) {  // 尾重复
                    prev.next = null;
                    return dHead.next;
                } else {// 中间重复
                    p1 = p2.next;
                    p2 = p2.next.next;
                    prev.next = p1;
                }

            } else {
                p1 = p1.next;
                p2 = p2.next;
                prev = prev.next;
            }
        }
        return dHead.next;
    }

    public ListNode deleteDuplicatesByRecursion(ListNode head) {
        if (head==null||head.next==null){
            return head;
        }
        if (head.val==head.next.val){
            ListNode p=head.next.next;
            //找到多个相等值的下一个位置指针
            while(p!=null&&p.val== head.val){
                p = p.next;
            }
            //返回此位置之后去重链表
            return deleteDuplicatesByRecursion(p);
        }else {
            //不相等 返回去重后的链表即可
            head.next=deleteDuplicatesByRecursion(head.next);
            return head;
        }
    }

    public static void main(String[] args) {

        ListNode t10 = new ListNode(8, null);
        ListNode t9 = new ListNode(8, t10);
        ListNode t8 = new ListNode(7, t9);
        ListNode t7 = new ListNode(7, t8);
        ListNode t6 = new ListNode(7, t7);
        ListNode t5 = new ListNode(6, t6);
        ListNode t4 = new ListNode(4, t5);
        ListNode t3 = new ListNode(4, t4);
        ListNode t2 = new ListNode(2, t3);
        ListNode t1 = new ListNode(1, t2);
        System.out.println(t1);
        Client82 client = new Client82();
        //System.out.println(client.deleteDuplicatesByRecursion(t1));
        //System.out.println(client.deleteDuplicates(t1));
    }
}